/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/reverse-words-in-a-string
   @Language: C++
   @Datetime: 16-02-09 05:17
   */

// Method 1, Time O(n), Space O(1), Time 346ms
class Solution {
public:
	/**
	 * @param s : A string
	 * @return : A string
	 * Tip:
	 * reverse each word, then reverse all string
	 */
	string reverseWords(string &s) {
		// write your code here
		stringstream istr(s);
		string res;
		for(string str; istr>>str;){
			reverse(str.begin(),str.end());
			res.append(str+" ");
		}
		reverse(res.begin(),res.end());
		return res.length()?res.substr(1):"";
	}
};


// Method 2, Time O(n), Space O(n), Time 118ms
class Solution {
public:
	/**
	 * @param s : A string
	 * @return : A string
	 * Tip: Stack
	 */
	string reverseWords(string &s) {
		// write your code here
		stringstream istr(s);
		stack<string> tmp;
		string res;
		for(string str; istr>>str; tmp.push(str));
		for(; tmp.size(); res.append(tmp.top()+" "), tmp.pop());
		if(res.back()==' ') res.pop_back();
		return res;
	}
};
